/*
124. 二叉树中的最大路径和
https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/
困难 2024/12/4
*/

class Solution {
    // 用于存储路径的最大和
    int maxSum = INT_MIN;

public:
    // 主函数，返回树中任意路径的最大和
    int maxPathSum(TreeNode* root) {
        // 调用辅助函数计算最大路径和
        maxValue(root);
        return maxSum;
    }

    // 辅助函数，返回以当前节点为根的最大单边路径和
    int maxValue(TreeNode* node) {
        if (node == nullptr) {
            return 0; // 空节点贡献值为0
        }

        // 计算左子树和右子树的最大单边路径和，忽略负值
        int left = max(0, maxValue(node->left));
        int right = max(0, maxValue(node->right));

        // 当前节点作为路径转折点时的最大路径和
        int pathSum = node->val + left + right;

        // 更新全局最大路径和
        maxSum = max(maxSum, pathSum);

        // 返回以当前节点为根的最大单边路径和
        return node->val + max(left, right);
    }
};